#ifndef TIM_AVLTREE_H
#define TIM_AVLTREE_H

#include "tim_bintree.h"
#include "tim_hashtable.h"
#include "tim_bst.h"

namespace tim
{
	#define balenced(x) ((x)->left->height == (x)->right->height)//简化语义判断并加速, 理想平衡
	#define balfac(x) ((x)->left->height - (x)->right->height)//平衡条件
	/*#define AvlBalanced(x) (!(x)->has_child()) or (-2 < balfac(x) and balfac(x) < 2) //平衡
	#define taller_child(x) ((x)->left->height > x->right->height? ((x)->left): \
							((x)->left->height != (x)->right->height ? ((x)->right): \
							(x)->parent->left == (x) ? ((x)->left): \
							((x)->right)))//取高孩子，同高则取同侧者*/
	#define is_left(x) ((x)->parent->left == (x))
	#define is_right(x) ((x)->parent->right == (x))
	//#define from_parent(x) ((x) == this->root? this->root: (is_left((x)) ? (x)->parent->left: (x)->parent->right))

	template<typename K, typename V>
	class AVLtree: public BST<K, V>
	{
		private:
			binnode<entry<K, V>>* _find(binnode<entry<K, V>>* next, K const& key);//迭代查找
			binnode<entry<K, V>>* connect34(binnode<entry<K, V>>* a, binnode<entry<K, V>>* b, binnode<entry<K, V>>* c,
											binnode<entry<K, V>>* T0, binnode<entry<K, V>>* T1, binnode<entry<K, V>>* T2, binnode<entry<K, V>>* T3);//3、4构成等效与zig、zag
			V error = V();//错误常量
			binnode<entry<K, V>>* rotate(binnode<entry<K, V>>* now);//同34构成一并进行统一重平衡
			bool AVLed(binnode<entry<K, V>>* g);
			binnode<entry<K, V>>* taller_child(binnode<entry<K, V>>* g);

		public:
			AVLtree(entry<K, V> const& e): BST<K, V>(e.key, e.value) {};
		    //AVLtree(entry<K, V>* begin, entry<K, V>* end): BST<K, V>(begin, end) {};//层次生成，必然平衡
			V remove(K const& key);//删除，时间复杂度O（
			binnode<entry<K, V>>* insert(K const& key, V const& value);
			int height() {return this->root->height; };
			V& find(K const& key) //对外find接口， 时间复杂度O（
			{
				binnode<entry<K, V>>* temp = _find(this->root, key);
				if (temp != NULL) return temp->data.value;
				else return error;
			};
	};
}

template<typename K, typename V>
tim::binnode<tim::entry<K, V>>* tim::AVLtree<K, V>::_find(tim::binnode<tim::entry<K, V>>* next, K const& key)
{
	this->hot = NULL;
	while (next != NULL) {
		this->hot = next;
		if (key < next->data.key) next = next->left;
		else if (key > next->data.key) next = next->right;
		else break;
	}

	return next;
}

template<typename K, typename V>
tim::binnode<tim::entry<K, V>>* tim::AVLtree<K, V>::connect34(binnode<entry<K, V>> *a, binnode<entry<K, V>> *b,
                                                              binnode<entry<K, V>> *c, binnode<entry<K, V>> *T0,
                                                              binnode<entry<K, V>> *T1, binnode<entry<K, V>> *T2,
                                                              binnode<entry<K, V>> *T3)
{
	a->left = T0; if (T0) T0->parent = a;
	a->right = T1; if (T1) T1->parent = a;
	this->update_height(a);

	c->left = T2; if (T2) T2->parent = c;
	c->right = T3; if (T3) T3->parent = c;
	this->update_height(c);

	b->left = a; a->parent = b;
	b->right = c; c->parent = b;
	this->update_height(b);

	return b;
}

template<typename K, typename V>
tim::binnode<tim::entry<K, V>>* tim::AVLtree<K, V>::rotate(tim::binnode<tim::entry<K, V>>* now)
{
	tim::binnode<tim::entry<K, V>>* p = now->parent;
	tim::binnode<tim::entry<K, V>>* g = p->parent;

	if (is_left(p)) {
		if (is_left(now)) {
			p->parent = g->parent;
			return connect34(now, p, g, now->left, now->right, p->right, g->right);
		}
		else {
			now->parent = g->parent;
			return connect34(p, now, g, p->left, now->left, now->right, g->right);
		}
	}
	else {
		if (is_right(now)) {
			p->parent = g->parent;
			return connect34(g, p, now, g->left, p->left, now->left, now->right);
		} else {
			now->parent = g->parent;
			return connect34(g, now, p, g->left, now->left, now->right, p->right);
		}
	}
}

template<typename K, typename V>
tim::binnode<tim::entry<K, V>>* tim::AVLtree<K, V>::taller_child(tim::binnode<tim::entry<K, V>>* g)
{
	if (g->has_both_child()) {
		if (g->left->height > g->right->height) return g->left;
		else if (g->left->height < g->right->height) return g->right;
		else if (g == this->root) return g->left;
		else if (g == g->parent->left) return g->left;
		else return g->right;
	} else if (g->left != NULL) return g->left;
	  else if (g->right != NULL) return g->right;
	  else return NULL;
};

template<typename K, typename V>
bool tim::AVLtree<K, V>::AVLed(binnode<entry<K, V>> *g)
{
	if (g->has_both_child()) return (-2 < balfac(g) and balfac(g) < 2);
	else if (g->left != NULL) return (g->left->height < 1);
	else if (g->right != NULL) return (g->right->height < 1);
	else return true;
}

template<typename K, typename V>
tim::binnode<tim::entry<K, V>>* tim::AVLtree<K, V>::insert(K const& key, V const& value)
{
	tim::binnode<tim::entry<K, V>>* x = _find(this->root, key);
	if (x != NULL) return x;

	this->_size++;
	x = new tim::binnode<tim::entry<K, V>>(entry<K, V>(key, value), this->hot);
	if (x->data < this->hot->data) this->hot->left = x;
	else this->hot->right = x;

	for (tim::binnode<tim::entry<K, V>>* g = this->hot; g != nullptr; g = g->parent) {
		if (!AVLed(g)) {
			if (g->parent == NULL) this->root = rotate(taller_child(taller_child(g)));
			else if (g->parent->left == g) g->parent->left = rotate(taller_child(taller_child(g)));
			else g->parent->right = rotate(taller_child(taller_child(g)));
			break;
		} else
			this->update_height(g);
	}

	return x;
}

template<typename K, typename V>
V tim::AVLtree<K, V>::remove(K const& key)
{
	tim::binnode<tim::entry<K, V>>* x = _find(this->root, key);
	if (x == NULL) return error;

	V temp = x->data.value;
	this->removeAt(x);
	this->_size--;
	
	for (tim::binnode<tim::entry<K, V>>* g = this->hot; g != nullptr; g = g->parent) {
		if (!AVLed(g)) {
			if (g->parent == NULL) this->root = rotate(taller_child(taller_child(g)));
			else if (g->parent->left == g) g->parent->left = rotate(taller_child(taller_child(g)));
			else g->parent->right = rotate(taller_child(taller_child(g)));
			break;
		} 
		this->update_height(g);
	}

	return temp;
}

#endif
